The prior art is replete with a number of error correcting code mechanisms. The codes are generally known as "hamming" codes in recognition of their early definition by R. P. Hamming of Bell Labs in the late 1940s. Such basic codes are described in "Error Detecting and Error Correcting Codes," Bell System Technical Journal, pp. 140-147, April 1950, and an example appears in the Ralston and Meek Encyclopedia of Computer Science, pp. 547-548.
An error correcting code is the data representation allowing for error detection and correction if the detected error is of a specific type. A common type of approach, shown in FIGS. 1 and 2 employs a data word using a code of seven binary digits. When the data word is correctly coded it will have a unique representation but changing any bit will produce a different and unacceptable coded character. Accordingly, in the case of a seven binary digit word there is a possibility of seven unacceptable characters relating to any single correctly coded character. During storage if any bit is changed, an error results. During reading of the word, detection of the error occurs by the use of a plurality of parity check bits generated for each multiple bit data word. These parity bits are written into storage together with the data word. FIG. 1 shows generally how such a data word together with parity check bits are used in assembling a so-called "H-Matrix."
As shown in FIG. 1, the seven binary digit word is divided into three check bits and four data bits. The "1" marks in a given horizontal row indicate bits which are checked by a particular parity bit. In FIG. 1, the first row parity check 1 is assigned for the 3, 5, and 7 data bits, second row parity check 2 for 3, 6 and 7 data bits and third row parity check 4 for the 5, 6, and 7 data bits. In the matrix, the binary sum of any check bits is indicative of the particular data bit. For example, an error occurring at the fifth bit would be subject to a parity check of bits 1 and 4, an error at the seventh bit would be subject to a parity check of bits 1, 2 and 4. As a result, the parity checks are given an appropriate weighting factor as shown in FIG. 1 and then by means of parity check circuits the truth table as shown in FIG. 2 can be used to determine the exact storage output bit error.
For example, if the output bit 6 is in error, parity check circuit 1 will indicate no error while parity checks 2 and 3 having weights 2 and 4 will indicate that the 6 bit is in error.
FIGS. 3 and 4 show a hardware implementation for the H-matrix of the FIG. 1. This hardware implementation also conforms to the Hamming code shown on page 548 of the "Encyclopedia of Computer Science" article identified above. As indicated, it is necessary to provide three check bits for a four-bit data character to achieve a single bit error correction operation. As shown in the H-matrix of FIG. 1 seven bits are stored for each data word. In FIG. 3, the seven bit storage element utilizes two inputs, the first being the four-bit data character comprising bit positions 3, 5, 6, and 7 and three check bits occupying bit positions 1, 2 and 4. The check bits, that is, bit 1, bit 2 and bit 4 are derived utilizing parity generators coupled logically in accordance the H-Matrix to respective bit channels of a bus carrying the four-bit data character. The generated check bits are then fed to the read-in side of the storage module.
On the read-out side, three parity check circuits are selectively coupled as shown to the seven bit data character to generate a three-bit binary code representative of the location or number of the storage unit output bit position which has produced an error. A decoder receives these three "syndrome bits" to activate one of seven possible output lines. That is, the decoder produces an output corresponding to the truth table of FIG. 4 upon receiving the three syndrome bits to indicate the error position. An error corrector, generally Exclusive OR circuits, receives the decoder output and each of the seven bits from storage. If, for example, a decoder output line has a "Zero" value, the corresponding Exclusive OR circuit will pass the storage output bit at that position in an unmodified value. If, however, the decoder output line has a "1" value, then the Exclusive OR circuit will invert the binary value of the storage bit passing through that circuit and, thereby, correct the error. In such systems it is apparent that only one of the decoder output lines will carry the "1" level at any one time, that is, corresponding to one erroneous bit position. That particular signal on the output line is used to correct the erroneous storage output bit by inversion to the opposite binary value.
Both check bits as well data error bits are corrected, however, if more than one bit is in error the mechanism fails. The system shown in FIG. 3 is known as a single error correction (SEC) system. These systems are used to correct data words which have only a single bit in error and multiple errors are beyond the capacity of such systems. A hallmark of such systems is the correspondence between parity checking circuits and parity generating circuit. For example, the parity generating circuit responsive to the first bit utilizes data bits 3, 5 and 7. The parity check circuit utilizes the same data bits, 3, 5 and 7 in addition to the first check bit (Bit 1). The same relationship exists for parity check circuit 2 in relationship to the bit 2 in parity check circuit 3 with respect to parity check bit 4.
An extension of the SEC system is an error-correcting code which will detect double errors, that is, a pair of erroneous bits in a single word and provide a signal indicative of that multiple error. Such systems are known in the prior art as a single error correction-double error detection (SEC-DED) systems.
Referring to FIGS. 5 and 6, a prior art system of this type is shown. FIGS. 5 and 6 correspond to the error-correcting code described in Hsiao, "A Class of Optimal Minimum Odd-Weight-Column SEC-DED Codes," I.B.M. Journal of Research and Development, July 1970, pp. 395-401. This SEC-DED system, a contemporary prior art technique, utilizes sixteen data bits and six check bits so that the total number of bits written into and ultimately read from the storage unit is a twenty-two bit word. As recognized in Hsiao, the generation of the H-Matrix shown in FIG. 6 follows specific criteria. The H-Matrix is a code having minimum weight w so that if every combination of w-1 or fewer columns of the matrix is linearly independent. The minimum weight requirement is recognized in the prior art as 4 thereby requiring that three or fewer columns of the H-matrix be linearly independent.
In the construction of the code shown in FIG. 6, three general constraints are imposed: (1) each column has an odd number of ones, that is, all column vectors are of odd weight, (2) the total number of ones in the H-matrix should be minimized and (3) the number of ones in each row of the matrix should be equal or as close as possible to the average number, that is, the total number of ones in the matrix divided by the number of rows. The H-matrix of FIG. 6, satisfying these constraints, utilizes six columns corresponding to the six possible combinations of one out of six and sixteen columns corresponding to sixteen of the twenty possible combinations of three out of six parity checks. By inspection, it can be seen that the total number of ones in the H-matrix is equal to three ones for each of sixteen columns plus six check pits equaling fifty-four ones. The average number of ones in each row is fifty-four divided by six or nine ones. Accordingly, in constructing a detection system for this H-Matrix a three-way Exclusive-OR gate can be used with a check and syndrome bits generated in two levels.
As shown in FIG. 5, the data word comprises sixteen data bits. In accordance with conventional practice the /16 indicates the number of bit lines in that data bus. The data word is supplied to a check bit generator comprising, in accordance with the Hsiao teaching, nineteen three-way Exclusive-OR circuits. The generator output comprises six check bits combined with the sixteen bit data word to form a twenty-two bit data word fed into storage. On the read out side, the twenty-two bit word, in a manner comparable with FIG. 3 is fed to a syndrome bit generator to perform the six parity checks. The six parity check circuits are comparable to the three parity check system shown in FIG. 1, that is, each system utilizing one parity check circuit for each check bit.
In accordance with Hsiao, in addition to single error correction, utilizing the decoder and error corrector as shown in FIG. 5, double error detection takes place. Double-error detection is accomplished by examining the overall parity of all syndrome bits generated by the syndrome bit generator. That is, the syndrome bit generator will generate an output to the decoder for purposes of correcting a single detected output error. Checking occurs by determining whether an even number of syndrome bits is generated thereby indicating an even number of errors. Because the errors are assumed to be statistically independent, multiple even errors are treated as though a double error has been sensed. Double error detection as shown in FIGS. 5 and 6 is different from the Hamming code as shown in FIGS. 1-4 since, a special bit, namely a fourth check bit together with a fourth parity checking circuit would be needed to realize an all-one row in the H-Matrix to determine whether a single (odd) or double (even) error has occurred.
Although the FIG. 5 circuit utilizes a separate circuitry for the check bit generator and syndrome bit generator, the prior art perceives that the same set of 19 Exclusive OR (EOR) circuits can be used to provide both the check bit generation and syndrome bit generation function. In this situation the check bit inputs C.sub.1 -C.sub.6 would be omitted when writing to storage but would be included in the syndrome bit generation phase. If such a system were utilized a switching circuit would be needed to switch the EOR circuits from a storage writing operation to a storage reading operation and therefore, from a practical standpoint the prior art generally uses separate circuitry.
Additionally, as shown in FIG. 6, the 6-bit code produced by the syndrome bit generator does not have the binary 8-4-2-1 weighting relationship relative to the bit number or position number of the erroneous storage output unit bit. However, as shown, for each of the sixteen data bit positions there is a discrete 6-bit code value for each different possible erroneous bit location. Accordingly, the decoder utilizing 22 AND circuits is correct so long as the 22 decoder output lines are correctly coupled to the different Exclusive OR circuits in the error corrector.
Although operative for SEC-DED, the prior art as shown in FIGS. 5 and 6 requires six check bits. Given the accepted use, high density storage and the corresponding requirement for an error-correcting code mechanism, the penalty for such additional circuits is fairly substantial. A system which reduces the number of check bits per word results in substantial savings in cost and number of circuits in the context of an overall system. For example, in a system utilizing 64K bytes (8 bits per byte) of storage, the elimination of one check bit saves 32K bits of storage.
In addition to Hsiao the prior art systems achieving SEC or SEC-DED are known. For example, U.S. Pat. No. 4,005,405 employs a modified Hamming using 5 check bits for a 26 bit data word to achieve SEC. However, double error detection is not perceived or employed in that system. U.S. Pat. No. 4,139,148 employs SEC-DED and divided a common RAM into separate data and check bit locations. The H-Matrix and hardware implementation used makes no attempt to minimize the number of check bits, using 7 check bits for 38 data bits. This patent follows the table in Hsiao (p. 397) for various code parameters. A second tier of prior art, considered less pertinent is also known. This includes U.S. Pat. Nos. 3,735,105; 3,949,208 and IBM Technical Disclosure Bulletins, Vol. 10, No. 10, pp. 1561-2; Vol. 15, No. 1, pp. 130-4; Vol. 20, No. 8, pp. 3187-8; Vol. 21, No. 10, pp. 4297-8; Vol. 22 , No. 4, pp. 1607-13, and Vol. 22, No. 88, pp. 3833-4. These systems while showing a number of alternatives do not deal with the problem of alpha particle errors in high density storage units, nor do they attempt to minimize the number of check bits for a given data word yet still accomplish SEC-DED. Six check bits for a sixteen bit data word have been required in all known operative systems working in this mode.